#include <iostream>
#include <vector>
#include <math.h>
using namespace  std;
class Solution {
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        int m = nums1.size();
        int n = nums2.size();
        vector<int>* res = nullptr;
        for(int chooseK = max(0, k - n); chooseK <= min(m, k); chooseK++){
            vector<int> resFirst;
            vector<int> resSecond;
            unitMaxVec(nums1, chooseK, resFirst);
            unitMaxVec(nums2, k - chooseK, resSecond);
            // if(chooseK == 1) return resFirst;
            vector<int>* resMerge = merge(resFirst, resSecond);

            if(res == nullptr) res = resMerge;
//            if(chooseK == 1)
//                return resFirst;
            else if(compareAll(res, resMerge)){
                delete resMerge;
            }
            else{

                delete res;
                res = resMerge;
            }

        }
        return *res;
    }

    void unitMaxVec(vector<int>& nums, int k, vector<int>& res){
        int count = 0;
        if(k == 0) return;
        for(int i = 0; i < nums.size(); i++){
            if(i == 0 || count + nums.size() - i == k){
                res.push_back(nums[i]);
                count++;
                continue;
            }
            while(!res.empty() && nums[i] > res.back() && count + nums.size() - i > k){
                res.pop_back();
                count--;
            }
            if(count < k){
                res.push_back(nums[i]);
                count++;
            }
        }
    }
    vector<int>* merge(vector<int>& nums1, vector<int>& nums2){
        vector<int>* res = new vector<int>;
        if(nums1.size() == 0){
            *res = nums2;
            return res;
        }
        if(nums2.size() == 0){
            *res = nums1;
            return res;
        }
        int one = 0;
        int two = 0;
        for(int i = 0; i < nums1.size() + nums2.size(); i++){
            if(one == nums1.size()) res->push_back(nums2[two++]);
            else if(two == nums2.size()) res->push_back(nums1[one++]);
            else if(nums1[one] < nums2[two]) res->push_back(nums2[two++]);
            else if(nums1[one] > nums2[two]) res->push_back(nums1[one++]);
            else{
                int signal = 0;
                int newOne = one;
                int newTwo = two;
                while(newOne < nums1.size() && newTwo < nums2.size()){
                    if(nums1[newOne] < nums2[newTwo]){
                        signal = 1;
                        break;
                    }
                    else if(nums1[newOne] > nums2[newTwo]){
                        signal = 2;
                        break;
                    }
                    else{
                        newOne++;
                        newTwo++;
                    }
                }
                if(signal == 1){
                    res->push_back(nums2[two++]);
                }
                else res->push_back(nums1[one++]);
            }
        }
        return res;
    }
    bool compareAll(vector<int>* vec1, vector<int>* vec2){
        int m = vec1->size();
        int i = -1;
        while(++i != m){
            if(vec1[i] > vec2[i]) return true;
            else if(vec1[i] < vec2[i]) return false;
        }
        return true;
    }
};
int main() {
    Solution solve;
//    vector<int> input1 = {3,4,6,5};
//    vector<int> input2 = {9,1,2,5,8,3};
    vector<int> input1 = {5,7,3};
    vector<int> input2 = {4,2,3};
    vector<int>* test = &input1;
    std::cout<<(*test)[1]<<endl;
    int k = 3;
    vector<int> res = solve.maxNumber(input1, input2, k);
    int aa = 5;
}
